package com.hc.programming.tree;

import com.hc.programming.util.ArrayUtil;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 * <p>
 * 示例 1:
 * <a href="./二叉树的层序遍历-示例1.png">示例1</a>
 * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
 * 输出：[3,9,20,null,null,15,7]
 * 示例 2:
 * 输入：inorder = [-1], postorder = [-1]
 * 输出：[-1]
 * <p>
 * 提示:
 * 1 <= inorder.length <= 3000
 * postorder.length == inorder.length
 * -3000 <= inorder[i], postorder[i] <= 3000
 * inorder 和 postorder 都由 不同 的值组成
 * postorder 中每一个值都在 inorder 中
 * inorder 保证是树的中序遍历
 * postorder 保证是树的后序遍历
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/15 11:07
 */
public class 从中序与后序遍历序列构造二叉树 {
    public static void main(String[] args) {
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        int[] postorder = new int[]{9, 15, 7, 20, 3};
        System.out.println(Arrays.toString(inorder) + "--" + Arrays.toString(postorder) + "=[3,9,20,null,null,15,7],--" + ArrayUtil.toString(buildTree(inorder, postorder)));
        inorder = new int[]{-1};
        postorder = new int[]{-1};
        System.out.println(Arrays.toString(inorder) + "--" + Arrays.toString(postorder) + "=[-1],--" + ArrayUtil.toString(buildTree(inorder, postorder)));
    }

    /**
     * 根据中序遍历和后序遍历，构造二叉树
     * 思路：
     * 1. 后序遍历的最后一个元素为根节点
     * 2. 在中序遍历中找到根节点的位置，左边为左子树，右边为右子树
     * 3. 递归构造左右子树
     * 4. 返回根节点
     *
     * @param inorder   中序遍历节点值数组
     * @param postorder 后序遍历节点值数组
     * @return 根节点
     */
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;

        // 方案一：找到根节点位置，裁剪数组
//        return 裁剪(inorder, postorder);

//        // 方案二：根据根节点位置，传入范围递归构造左右子树
//        return 范围处理(inorder, 0, inorder.length, postorder, 0, postorder.length);

        // 方案三：基于方案二，优化代码
        for (int i = 0; i < inorder.length; i++) {
            cache.put(inorder[i], i);
        }
        return 范围优化(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    // [inorder值, index]
    private static Map<Integer, Integer> cache = new HashMap<>();

    private static TreeNode 范围优化(int[] inorder, int start1, int end1, int[] postorder, int start2, int end2) {
        TreeNode root = new TreeNode(postorder[end2 - 1]);
        if (end1 - start1 == 1) return root;
        int index = cache.get(root.val);
        int dff = index - start1;
        if (start1 < index)
            root.left = 范围优化(inorder, start1, index, postorder, start2, start2 + dff);
        if (index + 1 < end1)
            root.right = 范围优化(inorder, index + 1, end1, postorder, start2 + dff, end2 - 1);
        return root;
    }

    private static TreeNode 范围处理(int[] inorder, int start1, int end1, int[] postorder, int start2, int end2) {
        TreeNode root = new TreeNode(postorder[end2 - 1]);
        if (end1 - start1 == 1) return root;
        int index = 0;
        for (int i = start1; i < end1; i++) {
            if (inorder[i] == root.val) {
                index = i;
                break;
            }
        }
        int dff = index - start1;
        if (start1 < index)
            root.left = 范围处理(inorder, start1, index, postorder, start2, start2 + dff);
        if (index + 1 < end1)
            root.right = 范围处理(inorder, index + 1, end1, postorder, start2 + dff, end2 - 1);
        return root;
    }

    private static TreeNode 裁剪(int[] inorder, int[] postorder) {
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        int index = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val) {
                index = i;
                break;
            }
        }
        if (index != 0)
            root.left = 裁剪(Arrays.copyOfRange(inorder, 0, index), Arrays.copyOfRange(postorder, 0, index));
        if (index + 1 < inorder.length)
            root.right = 裁剪(Arrays.copyOfRange(inorder, index + 1, inorder.length), Arrays.copyOfRange(postorder, index, postorder.length - 1));
        return root;
    }
}
